Young programmer
Sasha wrote his first testing system. He was so excited that it successfully
compiled that he decided to invite his school friends to his own contest.
However, at the
end of the round, it turned out that the system could not sort the teams in the
results table. Help Sasha implement this sorting.
Teams are
ordered according to ICPC rules:
·
By the number of solved problems in descending order;
·
If the number of solved problems is the same, sort by penalty time
in ascending order;
·
If all the previous criteria are equal, sort by team number in ascending
order.
Input. The first line contains the number of teams n (1 ≤ n ≤ 105) participating in the contest. In the i-th of the following n lines, the number of solved problems s (0 ≤ s ≤ 100) and penalty time t (0 ≤ t ≤
105) for the team with number i are given.
Output. Print n integers –
the team numbers in sorted order.
|
Sample
input |
Sample
output |
|
5 3 50 5 720 1 7 0 0 8 500 |
5 2 1 3 4 |
sort
We’ll represent a team as
a structure containing the following fields:
·
team number;
·
penalty time;
·
number of solved problems;
To solve the problem, it is necessary to implement a comparator – a
function that compares two teams according to the ICPC rules, and then perform
the sorting.
Declare a team structure –
an ICPC competition participant, including the team number, penalty time, and
number of solved problems.
struct person
{
int id,
penalty_time, problems;
} *acm;
Implement the function cmp
– a comparator for sorting the competition participants.
int cmp(person a, person b)
{
Sort by the number of solved problems in descending order.
if
(a.problems != b.problems) return a.problems
> b.problems;
If the number of solved problems is equal, sort by penalty time in
ascending order.
if
(a.penalty_time != b.penalty_time)
return
a.penalty_time < b.penalty_time;
If all previous criteria are equal, sort by team number in ascending
order.
return a.id
< b.id;
}
The main part of the
program. Allocate memory for the array of teams.
scanf("%d",&n);
acm = new person[n];
Read the data about the teams.
for (i = 0; i < n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
Sort the teams according to the given conditions.
sort(acm,acm+n,cmp);
Print the team numbers in the order of their placement in the results
table.
for (i = 0; i < n; i++)
printf("%d ",acm[i].id);
printf("\n");
delete[] acm;
Algorithm implementation – vector
Declare a team structure –
an ICPC competition participant, including the team number, penalty time, and
number of solved problems.
struct person
{
int id,
penalty_time, problems;
};
Declare an array of teams acm.
vector<person>
acm;
Implement the function cmp
– a comparator for sorting the competition participants.
int cmp(person a, person b)
{
Sort by the number of solved problems in descending order.
if
(a.problems != b.problems) return a.problems
> b.problems;
If the number of solved problems is equal, sort by penalty time in
ascending order.
if
(a.penalty_time != b.penalty_time)
return
a.penalty_time < b.penalty_time;
If all previous criteria are equal, sort by team number in ascending
order.
return a.id
< b.id;
}
The main part of the
program. Read the input data.
scanf("%d",&n);
acm.resize(n);
for (i = 0; i < n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
Sort the teams according to the given conditions.
sort(acm.begin(),acm.end(),cmp);
Print the team numbers in the order of their placement in the results
table.
for (i = 0; i < n; i++)
printf("%d
",acm[i].id);
printf("\n");
#include <cstdio>
#include <algorithm>
using namespace std;
int n, i, ptr;
struct person
{
int id,
penalty_time, problems;
int operator< (const
person &a) const
{
if
(problems != a.problems) return problems >
a.problems;
if
(penalty_time != a.penalty_time)
return
penalty_time < a.penalty_time;
return id
< a.id;
}
} *acm;
int main(void)
{
scanf("%d",&n);
acm = new
person[n];
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
sort(acm,acm+n);
for(i = 0; i
< n; i++)
printf("%d
",acm[i].id);
printf("\n");
delete[] acm;
return 0;
}
Java implementation
import java.util.*;
class Person
{
int problems;
int penalty_time;
int id;
public Person(int problems, int penalty_time, int id)
{
this.problems = problems;
this.penalty_time = penalty_time;
this.id = id;
}
}
public class Main
{
public static class MyFun implements Comparator<Person>
{
public int compare(Person a, Person b)
{
if (a.problems == b.problems && a.penalty_time == b.penalty_time) return a.id - b.id;
if (a.problems == b.problems) return a.penalty_time - b.penalty_time;
return b.problems - a.problems;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Person[] p = new Person[n];
for (int i = 0; i < n; i++)
p[i] = new Person(con.nextInt(), con.nextInt(), i+1);
Arrays.sort(p, new MyFun());
for (int i = 0; i < n; i++)
System.out.print(p[i].id + " ");
con.close();
}
}
Python implementation
Read the number of teams n.
n = int(input())
Build the list of teams teams.
Each team is represented as a tuple in the format:
(number of problems solved, total
penalty minutes, team number)
teams = []
for id in range(1, n + 1):
problems, penalty_times = map(int, input().split())
teams.append((problems, penalty_times, id))
Sort the teams according to the given conditions.
teams.sort(key = lambda
team: (-team[0], team[1], team[2]))
Print the team numbers in the order they appear in the final ranking.
for t in teams:
print(t[2], end = ' ')